//一个整型数组 nums 里除两个数字之外，其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。 
//
// 
//
// 示例 1： 
//
// 输入：nums = [4,1,4,6]
//输出：[1,6] 或 [6,1]
// 
//
// 示例 2： 
//
// 输入：nums = [1,2,10,4,1,4,3,3]
//输出：[2,10] 或 [10,2] 
//
// 
//
// 限制： 
//
// 
// 2 <= nums.length <= 10000 
// 
//
// 
// Related Topics 位运算 数组 👍 532 👎 0

package com.cute.leetcode.editor.cn;
public class ShuZuZhongShuZiChuXianDeCiShuLcof {
    public static void main(String[] args) {
        Solution solution = new ShuZuZhongShuZiChuXianDeCiShuLcof().new Solution();
    }
    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        /**
         * tnnd，跟我玩阴的是吧，那我也不演了，直接来吧！（看题解，位运算是真看不出来）
         * 数组中只有两个数字出现了一次，其他都出现了两次
         * 时间复杂度为N，空间复杂度为1
         * 思路是这样的：利用 x^x = 0的这个性质
         *  1.遍历数组，将所有的数字进行异或，最终得到的结果即为仅出现一次的元素的异或值
         *  2.由于两个元素不同，所以异或值一定不为0，找到异或值的第一位1，按照这一位对原始数组进行分割
         *  3.在分割的数组中分别异或，就可以将两个数分出来了
         */
        public int[] singleNumbers(int[] nums) {
            int diff = 0;
            for (int num : nums) diff ^= num;//异或最后可以剩下两个数的异或值
            diff &= -diff;// 取到两个数不同的第一位 -diff为diff的反码（包括最高位按位取反）+1
            int[] res = new int[2];
            for (int num : nums){
                // 区分两个数
                if ((diff & num) == 0) res[0] ^= num;
                else res[1] ^= num;
            }
            return res;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}